//LRU Cache
/*
设计一个固定大小的， 最少最近使用缓存 (least recently used cache, LRU)。每次将信息插入未
满的缓存的时候，以及更新或查找一个缓存内存在的信息的时候，将该信息标为最近使用。在缓
存满的情况下将一个新信息插入的时候，需要移除最旧的信息，插入新信息，并将该信息标为最
近使用

输入输出样例
	以下是数据结构的调用样例。给定一个大小为 n 的缓存，我们希望其使用最少最近使用策略
进行数据储存

LRUCache cache = new LRUCache( 2 ); //capacity
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
*/

//
class LRUCache
{
	unordered_map<int, list<pair<int, int>>::iterator> hash; //
	list<pair<int, int>> cache;
	int size;

public:
	LRUCache(int capacity) : size(capacity) {}
	int get(int key)
	{
		auto it = hash.find(key);
		if (it == hash.end())
		{
			return -1;
		}
		cache.splice(cache.begin(), cache, it->second);
		return it->second->second;
	}
	void put(int key, int value)
	{
		auto it = hash.find(key);
		if (it != hash.end())
		{
			it->second->second = value;
			return cache.splice(cache.begin(), cache, it->second);
		}
		cache.insert(cache.begin(), make_pair(key, value));
		hash[key] = cache.begin();
		if (cache.size() > size)
		{
			hash.erase(cache.back().first);
			cache.pop_back();
		}
	}
};
